

import java.util.ArrayList;
import java.util.HashMap;


public class Prim {
    public static ArrayList<Road> prim(int num, HashMap<Integer, Intersection> int2Index, HashMap<String, Road> roadHashMap) {  //num为顶点数，weight为权
        ArrayList<Road> res = new ArrayList<>();
        double[] lowcost = new double[num + 1];  //到新集合的最小权

        int[] closest = new int[num + 1];  //代表与s集合相连的最小权边的点

        boolean[] s = new boolean[num + 1];  //s[i] == true代表i点在s集合中

        s[1] = true;  //将第一个点放入s集合

        for (int i = 2; i <= num; i++) {  //初始化辅助数组
            lowcost[i] = getPrim(1, i, int2Index, roadHashMap);
            closest[i] = 1;
            s[i] = false;
        }
        double all = 0;
        for (int i = 1; i < num; i++) {
            double min = Float.MAX_VALUE;
            int j = 1;
            for (int k = 2; k <= num; k++) {
                if ((lowcost[k] < min) && (!s[k])) {//根据最小权加入新点
                    min = lowcost[k];
                    j = k;
                }
            }
            System.out.println("加入点" + int2Index.get(j).IntersectionId + ". " + int2Index.get(j).IntersectionId + "---" + int2Index.get(closest[j]).IntersectionId + "weight=" + getPrim(j, closest[j], int2Index, roadHashMap));//新加入点的j和与j相连的点
            res.add(roadHashMap.get(int2Index.get(j).IntersectionId + int2Index.get(closest[j]).IntersectionId));
            all = all + getPrim(j, closest[j], int2Index, roadHashMap);
            s[j] = true;//加入新点j

            for (int k = 2; k <= num; k++) {
                if ((getPrim(j, k, int2Index, roadHashMap) < lowcost[k]) && !s[k]) {//根据新加入的点j,求得最小权
                    lowcost[k] = getPrim(j, k, int2Index, roadHashMap);
                    closest[k] = j;
                }
            }
        }
        System.out.println("总里程数" + all);//新加入点的j和与j相连的点
        return res;
    }

    private static double getPrim(int i, int j, HashMap<Integer, Intersection> int2Index, HashMap<String, Road> roadHashMap) {
        if (i == 0 || j == 0) {
            return Double.MAX_VALUE;
        }
        String index = int2Index.get(i).IntersectionId + int2Index.get(j).IntersectionId;
        if (roadHashMap.containsKey(index)) {
            return roadHashMap.get(index).distance;
        } else {
            if (i == j) {
                return 0;
            } else {
                return Double.MAX_VALUE;
            }

        }
    }

//    public static void main(String[] args) {
//        //              ①
//        //            /  |  /
//        //           6   1   5
//        //          /    |    /
//        //        ②-5--③--5--④
//        //         /    //    /
//        //          3  6  4  2
//        //           //    //
//        //           ⑤--6-⑥
//        //最小生成树为：
//        //              ①
//        //               |
//        //               1
//        //               |
//        //        ②-5--③        ④
//        //         /     /    /
//        //          3     4  2
//        //           /     //
//        //           ⑤        ⑥
//        //
//        double m = Double.MAX_VALUE;
//        double[][] weight = {{0, 0, 0, 0, 0, 0, 0},
//                            {0, m, 6, 1, 5, m, m},
//                            {0, 6, m, 5, m, 3, m},
//                            {0, 1, 5, m, 5, 6, 4},
//                            {0, 5, m, 5, m, m, 2},
//                            {0, m, 3, 6, m, m, 6},
//                            {0, m, m, 4, 2, 6, m}};//上图的矩阵
//        prim(weight.length - 1, weight);
//        //加入点3. 3---1
//        //加入点6. 6---3
//        //加入点4. 4---6
//        //加入点2. 2---3
//        //加入点5. 5---2
//    }
}